package Beginners;

import java.util.Arrays;
import java.util.Scanner;

class AtkinSieve_1806
{	private int limit;
	private boolean isPrime[];
	private int prime[];
	
	public AtkinSieve_1806(int l)
	{	limit=(l>=5?l:5);
		MakeSieve();
	}
	private void MakeSieve()
	{	isPrime=new boolean[limit+1];
		Arrays.fill(isPrime, false);
		isPrime[2]=true;isPrime[3]=true;
		
		int cap=(int)Math.sqrt(limit);
		for (int x=1;x<=cap;x++)
			for (int y=1;y<=cap;y++)
			{	int n;
				n = 4*x*x+y*y;
				if (n<=limit && (n%12==1 || n%12==5))
					isPrime[n]=!isPrime[n];
				n = 3*x*x+y*y;
				if (n<=limit && n%12==7)
					isPrime[n]=!isPrime[n];
				n = 3*x*x-y*y;
				if (x>y && n<=limit && n%12==11)
					isPrime[n]=!isPrime[n];
			}
		for (int i=5;i<=cap;i++)
			if (isPrime[i])
				for (int j=1,t=i*i; t*j<=limit; j++)
					isPrime[t*j]=false;
		int k=0;
		for (int i=0;i<=limit;i++)
			if (isPrime[i]) k++;
		prime=new int[k];
		k=0;
		for (int i=0;i<=limit;i++)
			if (isPrime[i]) prime[k++]=i;
	}
	public int getPrime(int i)
	{	return prime[i-1];
	}
}
public class P1086
{	public static void main(String[] args)
	{	AtkinSieve_1806 aks=new AtkinSieve_1806(200000);
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		for (int i=0;i<n;i++)
			System.out.println(aks.getPrime(in.nextInt()));
		in.close();
	}
}
